package com.south.base.test.arithmetic.dynamic.programming;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Administrator
 * @date 2019/12/3 11:12
 */
public class Tree {
    /**
     * 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
     */
    @Test
    public void numTrees() {
        Assert.assertEquals(5, numTrees(3));
    }

    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;

        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }

    /**
     * 给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
     * TODO 没理解
     */
    @Test
    public void generateTrees() {
        generateTrees2(3);
    }

    public List<TreeNode> generateTrees2(int n) {
        //1.采用递归回溯的方法，情况比较复杂，同时存在重复计算
        //2.动态规划，dp[i]代表1-i节点组成的二叉搜索树，需要根据情况改变数值，遍历二叉树改变数值
        //3.动态规划，dp[i][j]代表长度为i，起点为j（j<n-i）的树的集合
        //List<TreeNode>[][] dp=new List<TreeNode>[n+1][n+1];不能创建list的数组
        //二维动态规划
        if (n == 0) {
            return new ArrayList<>();
        }
        List<List<List<TreeNode>>> lslsls = new ArrayList<>();
        //初始化动态规划数组
        List<List<TreeNode>> lsls0 = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            List<TreeNode> ls0 = new ArrayList<>();
            ls0.add(null);
            lsls0.add(ls0);
        }
        lslsls.add(lsls0);
        List<List<TreeNode>> lsls1 = new ArrayList<>();
        for (int i = 1; i < n + 1; i++) {
            List<TreeNode> ls1 = new ArrayList<>();
            ls1.add(new TreeNode(i));
            lsls1.add(ls1);
        }
        lslsls.add(lsls1);
        //开始计算，直到长度为n
        for (int m = 2; m < n + 1; m++) {
            //计算长度为m二叉树
            List<List<TreeNode>> lslsm = new ArrayList<>();
            for (int start = 1; start <= n - m + 1; start++) {
                //计算范围起点为start的二叉树
                List<TreeNode> list = new ArrayList<>();
                for (int x = start; x < m + start; x++) {
                    //计算根节点为x二叉树
                    List<TreeNode> tempL = lslsls.get(x - start).get(start - 1);//长度为x-1，起点为1
                    List<TreeNode> tempR = lslsls.get(m + start - x - 1).get(x);//长度为n-x，起点为x+1
                    for (TreeNode lNode : tempL) {
                        for (TreeNode rNode : tempR) {
                            TreeNode root = new TreeNode(x);
                            root.left = lNode;
                            root.right = rNode;
                            list.add(root);
                        }
                    }
                }
                lslsm.add(list);
            }
            lslsls.add(lslsm);
        }
        return lslsls.get(n).get(0);
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
